package practice_2025_9.practice_9_22;

import java.util.Arrays;

public class Sort {
    /**
     * 直接插入排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            // 当前插入元素
            int num = array[i];
            // 查找插入位置 (顺序)
            int j = i - 1;
            for(; j >= 0; j--) {
                if (array[j] > num) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = num;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public void shellSort(int[] array) {
        int len = array.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) {
                int num = array[i];
                int j = i - gap;
                for(; j >= 0; j -= gap) {
                    if (array[j] > num) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = num;
            }
        }
    }

    /**
     * 选择排序
     * 时间复杂度：最好、平均、最坏：O(n²)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public void chooseSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {
            int min = array[i];
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (array[j] < min) {
                    min = array[j];
                    minIndex = j;
                }
            }
//            System.out.println("min: " + min + " i:" + array[i]);
            // 交换 i 和 minIndex 位置元素
            swap(array, i, minIndex);
        }
    }
    public void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    /**
     * 堆排序
     * @param array
     */
    public void heapSort(int[] array) {
        int n = array.length;
        // 建立大根堆
        // 从最后一个非叶子节点开始调整
        for(int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        // 将堆顶（最大值）移到末尾，重新调整堆
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            // 对 [0, i) 范围堆重新堆化
            heapify(array, i, 0);
        }
    }

    private void heapify(int[] array, int heapSize, int rootIndex) {
        int largest = rootIndex;
        int left = 2 * rootIndex + 1;
        int right = 2 * rootIndex + 2;
        if (left < heapSize && array[left] > array[largest]) {
            largest = left;
        }
        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != rootIndex) {
            swap(array, rootIndex, largest);
            // 继续向下调整
            heapify(array, heapSize, largest);
        }
    }

    /**
     * 冒泡排序
     * @param array
     */
    public void bubbleSort(int[] array) {
        int len = array.length;
        boolean flg = true;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (array[j] > array[j +1]) {
                    swap(array, j, j + 1);
                    flg = false;
                }
            }
            if (flg) {
                break;
            }
        }
    }

    public void quickSort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int div = partion(array, begin, end);
        quickSort(array, begin, div - 1);
        quickSort(array, div + 1, end);
    }

    /**
     * 不可用先移动 left
     * 会导致在某些情况下（如数组已有序、或含大量相等元素）发生“错误交换”或“无限循环
     * @param array
     * @param begin
     * @param end
     * @return
     */
    private int partion(int[] array, int begin, int end) {
        int p = array[end];
        int left = begin, right = end;
        while (left < right) {
            while (left < right && array[left] <= p) {
                left++;
            }
            while (right > left && array[right] >= p) {
                right--;
            }
            swap(array, left, right);
        }
//        System.out.println("p: " + array[begin] + " " + left);
//        System.out.println(Arrays.toString(array));
        swap(array, left, end);
        return left;
    }

    public void mergeSort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = (begin + end) / 2;
        // 继续递归
        mergeSort(array, begin, mid );
        mergeSort(array, mid + 1, end);
//        System.out.println(Arrays.toString(array));
        // 合并 [begin,  mid - 1] 和 [mid, end]
        int[] tmp = new int[end - begin + 1];
        int b1 = begin, e1 = mid;
        int b2 = mid + 1, e2 = end;
        int cur = 0;
        while (b1 <= e1 && b2 <= e2) {
            if (array[b1] <= array[b2]) {
                tmp[cur++] = array[b1++];
            } else {
                tmp[cur++] = array[b2++];
            }
        }
        while (b1 <= e1) {
            tmp[cur++] = array[b1++];
        }
        while (b2 <= e2) {
            tmp[cur++] = array[b2++];
        }
//        System.out.println(Arrays.toString(tmp));
        for (int i = 0; i < tmp.length; i++) {
            array[begin + i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] arr = {1, 3, 4, 2, 0};
//        sort.insertSort(arr);
//        sort.shellSort(arr);
//        sort.chooseSort(arr);
//        sort.heapSort(arr);
//        sort.bubbleSort(arr);
//        sort.quickSort(arr, 0, arr.length - 1);
        sort.mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }
}
